package com.fenqing.leetcode.code.t200_300;

import com.fenqing.annotations.Execute;
import com.fenqing.core.Topic;

public class Topic278 extends Topic {

    int bad = 2;

    /**
     * 构造器
     * @param input 输入
     */
    public Topic278(String input) {
        super(input);
    }

    /**
     * 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
     * 假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
     * 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
     * 示例 1：
     * 输入：n = 5, bad = 4
     * 输出：4
     * 解释：
     * 调用 isBadVersion(3) -> false
     * 调用 isBadVersion(5) -> true
     * 调用 isBadVersion(4) -> true
     * 所以，4 是第一个错误的版本。
     * 示例 2：
     * 输入：n = 1, bad = 1
     * 输出：1
     * @param n n
     * @return return
     */
    @Execute
    public int firstBadVersion(int n) {
        int p = 1, q = n;
        while (p < q) {
            //计算中间值
            int mid = (int) (((long)p + q) >> 1);
            //判断前一个版本是否正确
            boolean bool1 = isBadVersion(mid - 1);
            boolean bool2 = isBadVersion(mid);
            if (!bool1 && bool2) {
                // 如果恰好前一个版本是好的，后一个版本是坏的，说明当前版本是第一个坏的版本
                return mid;
            } else if (!bool1) {
                // 如果前面的版本是好的，继续往后找
                p = mid + 1;
            } else {
                q = mid - 1;
            }
        }
        return p;
    }

    boolean isBadVersion(int version){
        return version >= bad;
    }

    public static void main(String[] args) {
        Topic278 topic278 = new Topic278("2");
        int run = topic278.run();
        System.out.println(run);
    }

}
